/*************************
 copyright @watofall
 no guarantee for bugfree!
**************************/

#include <iostream>
#include <fstream>
#include "string.h"
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_CHAR 100

typedef struct Pair
{
	char *val;
	char *next;
}Pair;

typedef struct NumVal
{
	int sequence;
	char *val;
}NumVal;

bool comp1(Pair a, Pair b)
{
	if(strcmp(a.val, b.val) < 0)
		return true;
	else
		return false;
}

bool comp2(Pair a, Pair b)
{
	if(strcmp(a.next, b.next) < 0)
		return true;
	else
		return false;
}

bool comp3(NumVal a, NumVal b)
{
	if(strcmp(a.val, b.val) < 0)
		return true;
	else
		return false;
}

bool comp4(NumVal a, NumVal b)
{
	return a.sequence < b.sequence;
}

int main() {
	ifstream fin ("sort_pair2.in");
	int i, j, k, count, t;
	char buf1[MAX_CHAR], buf2[MAX_CHAR];
	vector<Pair> pairs, pairs_b, pairs_, pairs_save;
	vector<NumVal> num_vals, num_vals_;

	for(i = 0; fin.good(); i ++)
	{
		fin >> buf1 >> buf2;

		Pair new_pair;

		new_pair.val = new char[strlen(buf1)];
		new_pair.next = new char[strlen(buf2)];
		strcpy(new_pair.val, buf1);
		strcpy(new_pair.next, buf2);
		pairs.push_back(new_pair);
	}
	count = i + 1;

	pairs_b = pairs;
	pairs_save = pairs;
	sort(pairs.begin(), pairs.end(), comp1);
	sort(pairs_b.begin(),pairs_b.end(), comp2);
	// find the last element
	for(i = 0, j = 0; j < count - 1;)
	{
		if(i >= count - 1) // find miss match
		{
			NumVal new_num_val;
			new_num_val.sequence = count;
			new_num_val.val = pairs_b[j].next;
			num_vals.push_back(new_num_val);
			j ++;
		}
		else if(strcmp(pairs_b[j].next, pairs[i].val) == 0) // find match
		{
			i ++;
			j ++;
		}
		else if(strcmp(pairs_b[j].next, pairs[i].val) > 0) // go on match to the next element
		{
			i ++;
		}
		else // find miss match
		{
			NumVal new_num_val;
			new_num_val.sequence = count;
			new_num_val.val = pairs_b[j].next;
			num_vals.push_back(new_num_val);
			j ++;
		}
	}

	// match and add
	for(t = 1; t <= count; t *= 2)
	{
		pairs_b = pairs;
		sort(pairs.begin(), pairs.end(), comp1);
		sort(pairs_b.begin(), pairs_b.end(), comp2);
		sort(num_vals.begin(), num_vals.end(), comp3);
		pairs_.clear();
		num_vals_ = num_vals;

		for(i = 0, j = 0, k = 0; i < count - t;)
		{
			if(j < count - t && strcmp(pairs_b[i].next, pairs[j].val) == 0) // pairs_b match pairs
			{
				Pair new_pair;
				new_pair.val = pairs_b[i].val;
				new_pair.next = pairs[j].next;
				pairs_.push_back(new_pair);
				i ++;
				j ++;
				continue;
			}

			if(k < num_vals.size() && strcmp(pairs_b[i].next, num_vals[k].val) == 0) // pairs_b match num_vals
			{
				NumVal new_num_val;
				new_num_val.sequence = num_vals[k].sequence - t;
				new_num_val.val = pairs_b[i].val;
				num_vals_.push_back(new_num_val);
				i ++;
				k ++;
				continue;
			}
			
			if(j < count - t && strcmp(pairs_b[i].next, pairs[j].val) > 0) // go on search pairs
			{
				j ++;
				continue;
			}
			
			if(k < num_vals.size() && strcmp(pairs_b[i].next, num_vals[k].val) > 0)
			{
				k ++;
				continue;
			}
		}

		pairs = pairs_;
		num_vals = num_vals_;
	}

	sort(num_vals.begin(), num_vals.end(), comp4);
	cout << "results :" << endl;
	for(i = 0; i < num_vals.size(); i ++)
	{
		cout << num_vals[i].val << " ";
	}
}